МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
Національний університет “Львівська політехніка”
Кафедра САП
Звіт
до лабораторної роботи № 1
РЕКУРСИВНІ ФУНКЦІЇ, ВКАЗІВНИКИ НА ФУНКЦІЇ В АЛГОРИТМІЧНІЙ МОВІ С
з курсу “Проблемно-орієнтоване програмування”
для студентів спеціальності "Комп’ютерні системи проектування"
Львів 2013
ТЕОРЕТИЧНІ ВІДОМОСТІ
Рекурсивні функції
Рекурсивним називається такий спосіб реалізації функції., коли функція може звертатися сама до себе. У рекурсивній функції повинні виконуватися наступні правила:
- при кожному виклику такої функції в неї повинні передаватися модифіковані дані;
- на якомусь етапі повинен бути припинений подальший виклик даної функції. Рекурсивний процес повинен крок за кроком так спрощувати завдання, щоб зрештою для нього з'явилося не рекурсивне рішення. Тут легко припуститися помилки, що полягає в тім, що функція буде послідовно викликати саму себе нескінченно довго;
після завершення кожного виклику рекурсивної функції в точку повернення повинен передаватися деякий результат для подальшого використання.
Вказівники на функції. Масиви вказівників на функції
У мові С сама функція не може бути значенням змінної, але можна визначити вказівник на функцію. З ним уже можна оперувати, як зі змінною: передавати його іншим функціям, поміщати в масиви й т.д. Оголошення виду:
int ( *fl ) ( );
говорить про те, що fl - вказівник на функцію, що повертає ціле значення. Перша пара дужок необхідна, без них
int *f 1 ( ); /* це не вказівник на функцію */
означало б, що fl -функція, що повертає вказівник на ціле значення. Після оголошення вказівник а на функцію в програмі можна використовувати оператори виду:
y = ( *fl ) ( . . .); або y = f1(...);
Вказівник на функцію - такий тип змінної, котрій можна присвоювати адреси точки входу у функцію, тобто адресу першої виконуваної команди. Ця змінна надалі може використовуватися для виклику функції замість її імені. Визначення вказівника на функцію має наступний загальний вид:
тип_результату (* ім'я вказівника на функцію) (список типів параметрів) ;
Наприклад:
double (*fd) ( int, int );
/* fd - покажчик на функцію, що повертає результат типу double і приймає два параметри типу int. */
int ( *find ) ( int, float * ) ;
/ find - вказівник на функцію. Функція повертає результат типу int і приймає два параметри: число типу int і вказівник на число типу float.*/
char* ( * comp ) ( const char *sl, const char *s2 ) ;
/* comp - вказівник на функцію, що повертає результат вказівник на char і приймаючу як параметри два вказівники на char.*/
При визначенні вказівника на функцію дозволяється одночасно із вказівкою типу параметрів задавати і їхні імена.
Нехай є прототипи функцій піднесення числа типу int у третю, п'яту і сьому степінь і які повертають результат типу int (звичайно, все це легко реалізувати й в одній функції):
int f3 ( int );
int f5 ( int ) ;
int f7 ( int );
і є вказівник на функцію наведеного вище виду:
int ( *fst ) ( int );
Тоді оператор fst = f3; присвоїть вказівнику fst адресу входу у функцію f3, fst = f5; - адресу входу у функцію f5 і, відповідно, fst = f7; - адресу входу у функцію f7. Після цього викликати кожну з функцій (f3, f5, f7) можна будь-яким оператором, записаним нижче (наприклад, f3):
f3 ( a ); // звертання до функції, використовуючи її ім'я.
(*fst ) ( а ); // виклик функції через вказівник.
fst( a ); // виклик функції також через вказівник.
Останній варіант також правильний, тому що f3, fst - це адреси входу у функцію. Однак виклик ( *fst ) ( а ) явно показує, що використовується вказівник на функцію, а не викликається функція з ім'ям fst, якщо бачити тільки один оператор fst ( a );.
У ряді задач, що використовують математичні методи, вказівник на функцію необхідно передавати як параметр у функцію, що реалізує відповідний метод. Наприклад, для обчислення значення інтеграла треба знати ім'я функції, у якій обчислюється значення підінтегрального виразу; для ...